package trees;

public class MyLinkedList {
    Node node;

    public class Node {
        // 当前值
        int val;
        // 后继节点
        Node next;
    }

    public int getNodeLength() {
        int length = 0;
        Node temp = this.node;
        while (temp != null) {
            temp = temp.next;
            length++;
        }

        return length;
    }


    /**
     * Initialize your data structure here.
     */
    public MyLinkedList() {
        this.node = new Node();
        this.node.val = -1;
        this.node.next = null;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
     */
    public int get(int index) {
        int nodeLength = getNodeLength();
        if (nodeLength - 1 < index) {
            return -1;
        }
        int i = 0;
        Node temp = this.node;
        while (temp != null) {
            if (i == index) {
                return temp.val;
            } else {
                temp = temp.next;
                i++;
            }
        }

        return -1;
    }

    /**
     * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(int val) {
        Node node = new Node();
        node.val = val;
        node.next = this.node;
        this.node = node;

        if (this.node.next != null) {
            if (this.node.next.val == -1) {
                this.node.next = null;
            }
        }
    }

    /**
     * Append a node of value val to the last element of the linked list.
     */
    public void addAtTail(int val) {
        Node tail = new Node();
        tail.val = val;
        tail.next = null;

        Node tempNode = this.node;

        while (this.node != null) {
            if (this.node.val == -1) {
                this.node = tail;
                return;
            }

            if (this.node.next != null) {
                this.node = this.node.next;
            } else {
                this.node.next = tail;
                this.node = tempNode;
                return;
            }
        }

    }

    /**
     * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
     */
    public void addAtIndex(int index, int val) {
        // 三种情况
        // 1，如果index == nodeLength，那么就在结尾添加val
        // 2，如果index > nodeLength，那么不会插入val
        // 3，如果index < 0，那么就在头部插入节点

        int nodeLength = this.getNodeLength();

        if (index > nodeLength) {
            return;
        }

        if (index <= 0) {
            addAtHead(val);
            return;
        }

        if (index == nodeLength) {
            addAtTail(val);
            return;
        }

        int insertIndex = 0;
        Node tempNode = this.node;

        while (this.node != null) {
            if (insertIndex == index) {
                int temp = this.node.val;
                this.node.val = val;
                Node node = new Node();
                node.val = temp;
                node.next = this.node.next;
                this.node.next = node;
                this.node = tempNode;
                return;
            } else {
                this.node = this.node.next;
                insertIndex++;
            }
        }
    }

    /**
     * Delete the index-th node in the linked list, if the index is valid.
     */
    public void deleteAtIndex(int index) {
        Node tempNode = this.node;
        int nodeLength = getNodeLength();
        if (nodeLength - 1 < index) {
            return;
        }

        int i = 0;
        while (this.node != null) {
            if (i == index) {
                if (this.node.next == null) {
                    this.node = null;
                } else {
                    this.node.val = this.node.next.val;
                    this.node.next = this.node.next.next;
                    this.node = tempNode;
                }
                return;
            } else {
                this.node = this.node.next;
                i++;
            }
        }
    }

    public static void main(String[] args) {
        String[] action = new String[]{
                "addAtHead", "addAtTail", "addAtTail", "addAtTail", "addAtTail", "addAtTail", "addAtTail", "deleteAtIndex", "addAtHead", "addAtHead", "get", "addAtTail", "addAtHead", "get", "addAtTail", "addAtIndex", "addAtTail", "addAtHead", "addAtHead", "addAtHead", "get", "addAtIndex", "addAtHead", "get", "addAtHead", "deleteAtIndex", "addAtHead", "addAtTail", "addAtTail", "addAtIndex", "addAtTail", "addAtHead", "get", "addAtTail", "deleteAtIndex", "addAtIndex", "deleteAtIndex", "addAtHead", "addAtTail", "addAtHead", "addAtHead", "addAtTail", "addAtTail", "get", "get", "addAtHead", "addAtTail", "addAtTail", "addAtTail", "addAtIndex", "get", "addAtHead", "addAtIndex", "addAtHead", "addAtTail", "addAtTail", "addAtIndex", "deleteAtIndex", "addAtIndex", "addAtHead", "addAtHead", "deleteAtIndex", "addAtTail", "deleteAtIndex", "addAtIndex", "addAtTail", "addAtHead", "get", "addAtIndex", "addAtTail", "addAtHead", "addAtHead", "addAtHead", "addAtHead", "addAtHead", "addAtHead", "deleteAtIndex", "get", "get", "addAtHead", "get", "addAtTail", "addAtTail", "addAtIndex", "addAtIndex", "addAtHead", "addAtTail", "addAtTail", "get", "addAtIndex", "addAtHead", "deleteAtIndex", "addAtTail", "get", "addAtHead", "get", "addAtHead", "deleteAtIndex", "get", "addAtTail", "addAtTail"
        };
        String actionNums = "[38],[66],[61],[76],[26],[37],[8],[5],[4],[45],[4],[85],[37],[5],[93],[10,23],[21],[52],[15],[47],[12],[6,24],[64],[4],[31],[6],[40],[17],[15],[19,2],[11],[86],[17],[55],[15],[14,95],[22],[66],[95],[8],[47],[23],[39],[30],[27],[0],[99],[45],[4],[9,11],[6],[81],[18,32],[20],[13],[42],[37,91],[36],[10,37],[96],[57],[20],[89],[18],[41,5],[23],[75],[7],[25,51],[48],[46],[29],[85],[82],[6],[38],[14],[1],[12],[42],[42],[83],[13],[14,20],[17,34],[36],[58],[2],[38],[33,59],[37],[15],[64],[56],[0],[40],[92],[63],[35],[62],[32]";
        MyLinkedList linkedList = new MyLinkedList();
        String[] nums = actionNums.split("],");
        for (int i = 0; i < action.length; i++) {
            String temp = nums[i].replace("]", "").replace("[", "");
            String act = action[i];
            switch (act) {
                case "addAtHead":
                    linkedList.addAtHead(Integer.parseInt(temp));
                    System.out.print("null ");
                    break;
                case "addAtTail":
                    linkedList.addAtTail(Integer.parseInt(temp));
                    System.out.print("null ");
                    break;
                case "deleteAtIndex":
                    linkedList.deleteAtIndex(Integer.parseInt(temp));
                    System.out.print("null ");
                    break;
                case "get":
                    if (temp.equals("40")) {
                        System.out.println(1);
                    }
                    int getVal = linkedList.get(Integer.parseInt(temp));
                    System.out.print(getVal + " ");
                    break;
                default:
                    String[] input = temp.split(",");
                    linkedList.addAtIndex(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
                    System.out.print("null ");
                    break;
            }
        }
    }
}
